アルゴリズム解析・設計 授業
■授業概要
アルゴリズムとは有限時間で問題を解くための一連の手順であり、明確に定義され順序づけられた有限個の規則の集合で定義される。これをコンピュータが解釈できる言語形式に変換したものがプログラムである。問題が与えられたとき、それを解く手順は一通りとは限らない。同じように正しい答えが出せても効率よく解けるアルゴリズムもあれば、効率の悪いアルゴリズムもある。
本科目では、整列や探索等の基本的なアルゴリズムとそれらが扱うデータ構造について詳説するとともに、よりよいアルゴリズムを設計するための解析法について講義する。
■到達目標
①知識・技能の観点
基本的なアルゴリズム Algorithmsとデータ構造 Data Structureを理解し、それらの特徴を説明できる。
②思考力・判断力・表現力等の能力の観点
基本的なアルゴリズムを解析、設計できる。
③主体的な態度の観点
理解が不十分な点についてを自ら復習し、理解度を高めることができる。
■授業計画
アルゴリズム解析・設計 授業 01
アルゴリズム解析・設計 授業 02
連結リスト Linked list 連想配列 辞書 object
アルゴリズム解析・設計 授業 03
アルゴリズム Algorithms
search 探索
線形探索 Linear search
二分探索 Binary search
アルゴリズム解析・設計 授業 04
search 探索
ハッシュ探索 hash search
ハッシュ関数 hash function
Hash Table ハッシュテーブル
アルゴリズム解析・設計 授業 05
アルゴリズム Algorithmsとオーダー order notation
アルゴリズム解析・設計 授業 06
データ構造 Data Structure
Stack スタックとQueue キュー
アルゴリズム解析・設計 授業 07
Recursion 再帰
自然数
最大公約数 Greatest common divisor
ユークリッドの互除法
トップダウン解析 top-down analysis
ボトムアップ解析 bottom-up analysis
フィボナッチ数列
アルゴリズム解析・設計 授業 08
メモ化 memorization
ハノイの塔
n-queeens
アルゴリズム解析・設計 授業 09
Sorting ソート 整列
Bubble Sort バブルソート
Selection Sort 選択ソート
挿入ソート Insertion sort
アルゴリズム解析・設計 授業 10
Sorting ソート 整列
Shellsort シェルソート
Quicksort クイックソート
分割統治法
アルゴリズム解析・設計 授業 11
分割統治法
Sorting ソート 整列
Merge Sort マージソート
Heap Sort ヒープソート
アルゴリズム解析・設計 授業 12
基数ソート radix sort
基数ソート radix sort
Bucket Sort バケットソート
アルゴリズム解析・設計 授業 13
Tree 木構造
アルゴリズム解析・設計 授業 14
Graph グラフ
第15回 まとめ
アルゴリズム解析・設計 期末課題
■基準・評価
①知識・技能の観点
基本的なアルゴリズムやデータ構造とそれらの特徴を理解しているかを評価する。
②思考⼒・判断⼒・表現⼒等の能⼒の観点
アルゴリズムを解析、設計できるかを評価する。
出席点なし
教科書
アルゴリズムを、はじめよう
参考書
Cによるアルゴリズムとデータ構造
新・明解C言語で学ぶアルゴリズムとデータ構造